
// 动态规划

// 题目描述
// 这是一场有预谋的盗窃活动。现在一条路上有一排房间，每个房间都有一些钱。盗窃不能同时出现在两个相邻的房间，否则会触发警报。

// 现在给定这些房间的钱的数量，问在不触动警报的情况下最多能拿到多少钱。

// 样例
// Example 1:

// Input: [1,2,3,1]
// Output: 4
// 解释: 盗窃房间 1 (钱数 = 1) 然后盗窃房间 3 (钱数 = 3).
//              盗窃的钱数总和 = 1 + 3 = 4.


// Example 2:

// Input: [2,7,9,3,1]
// Output: 12
// 解释: 盗窃房间 1 (钱数 = 2), 盗窃房间 3 (钱数 = 9) 然后盗窃房间 5 (钱数 = 1).
//              盗窃的钱数总和 = 2 + 9 + 1 = 12.


// 算法
// (动态规划) O(n)
// f[i]代表不盗窃第i个房间所能得到的最大收益， g[i]代表盗窃了第i个房间所能得到的最大收益
// f[i]的更新：上一个偷不偷都行，反正这个不偷
// g[i]的更新：上一个不偷，加上现在这个

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);
        for (int i = 1; i <= n; i ++ )
        {
            f[i] = max(f[i - 1], g[i - 1]);
            g[i] = nums[i - 1] + f[i - 1];
        }
        return max(f[n], g[n]);
    }
};
